package com.le.enhance.class1;

import org.junit.Test;

/**
 * 字符串最长回文子串
 */
public class Code_04_Manacher {

    // 暴力, 时间复杂度O(n * n)
    public static int getSubStringLength(String s) {
        if (s == null || s.length() == 0 || s.length() == 1) {
            return 0;
        }
        char[] chs = transfer(s.toCharArray());
        int max = 1;
        for (int i = 1; i < chs.length; i++) {
            int left = i - 1;
            int right = i + 1;
            while (left > -1 && right < chs.length) {
                if (chs[left] != chs[right]) {
                    break;
                }
                max = Math.max(max, right - left + 1);
                left--;
                right++;
            }
        }
        return max / 2;

    }


    // manacher 算法,时间复杂度O(n)
    public static int process(String s) {
        // s --> str #a#b#c#1#2#3#4#3#2#1#a#b#
//        char[] str = null;
//        int R = -1;
//        int C = -1;
//        int[] arr = new int[str.length];
//        int max = Integer.MIN_VALUE;
//        for (int i = 0; i < str.length; i++) {
//            if(i在R外部){  情况1
//                暴力扩,更新R,C
//            }else if (i对称点在L..R内部){ 情况2.1
//                arr[i]直接获得
//            }else if(i对称点回文区域一部分在L..R外部){  情况2.2
//                arr[i]直接获得
//            }else{
//                从R开始向外扩,之后确定arr  情况2.3
//            }
//        }
//
//        return max / 2;
        return 0;
    }

    public static int maxLcpsLength(String str) {
        if (str == null || str.length() == 0) {
            return 0;
        }
        char[] chs = transfer(str.toCharArray());
        int[] pArr = new int[chs.length]; // 回文半径数组 import
        int R = -1; // 向外扩最右边界
        int C = -1; // 中心点
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < chs.length; i++) {
            // 可以确定的回文半径数组 情况1, 2.1, 2.2
            pArr[i] = i < R ? Math.min(pArr[2 * C - i], R - i) : 1;

            // 把每一个位置都向后扩一次试试 整合所有情况
            while (i + pArr[i] < chs.length && i - pArr[i] > -1) {
                if (chs[i + pArr[i]] == chs[i - pArr[i]]) {
                    pArr[i]++;
                } else {
                    break;
                }
            }
            // i在R外部 --> 更新最右边界及中心点
            if (i + pArr[i] > R) {
                R = i + pArr[i];
                C = i;
            }
            max = Math.max(max, pArr[i]);

        }
        return max - 1;

    }

    public static char[] transfer(char[] chs) {
        StringBuffer sb = new StringBuffer();
        sb.append("#");
        for (int i = 0; i < chs.length; i++) {
            sb.append(chs[i] + "#");
        }
        return sb.toString().toCharArray();
    }

    @Test
    public void test() {
        String str = "ccbcabaabba";
        System.out.println(transfer(str.toCharArray()));
        System.out.println(getSubStringLength(str));
        System.out.println(maxLcpsLength(str));
    }
}
